/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item33;

import org.junit.Assert;
import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:VerifySquenceOfBST.java v1.0 2018/8/6 上午12:53 LvJing Exp $
 */
public class VerifySquenceOfBST {

    /**
     * 面试题33：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。
     * 假设输入的数组的任意两个数字都互不相同。
     * 思路：也是递归的典范例子。二叉搜索树也就是常说的二叉查找树，左子树比根节点小，右子树比根节点大。那么它的后序遍历结果的最后一位肯定是
     * 根节点，那么前面的序列可分成两段，一个是左子树，一个是右子树，左子树所有值均小于根节点，右子树所有值均大于根节点。参考这个特性就能分开
     * 这个序列为左子树和右子树，同时左子树和右子树各自的序列，依然满足后序遍历的形式，递归进行同样的操作。
     */
    public class Solution {
        public boolean VerifySequenceOfBST(int[] sequence) {
            if (sequence == null || sequence.length == 0)
                return false;
            if (sequence.length == 1)
                return true;

            return judge(sequence, 0, sequence.length - 1);
        }

        private boolean judge(int[] sequence, int start, int root) {
            if (start >= root)
                return true;

            int cur = root;
            // 从后向前，定位到左子树和右子树的分割点--左子树的最后一个元素，也是左子树的根节点
            while (cur > start && sequence[cur] >= sequence[root]) {
                cur--;
            }
            // 若左子树的值有大于根节点的，校验false
            for (int i = start; i < cur; i++) {
                if (sequence[i] > sequence[root])
                    return false;
            }
            return judge(sequence, start, cur) && judge(sequence, cur + 1, root - 1);
        }
    }

    @Test
    public void test01() {
        Solution solution = new Solution();
        int[] sequence = {2, 4, 3, 7, 5};

        Assert.assertTrue(solution.VerifySequenceOfBST(sequence));
    }
}
